#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N=1e6+7;
int x,y,n,m;
ll pp,xx;
int a[N];

#define ls(p) st[p<<1]
#define rs(p) st[p<<1|1]
#define ln    p<<1
#define rn    p<<1|1
#define cr    st[p]
#define mid  l+((r-l)>>1)

struct seg{
	ll s,a,m;
}st[N<<2];

void init(int p,int l,int r){
	cr.a=0;
	cr.m=1;
	if(l==r){
		cr.s=a[r];
		return ;
	}
	init(ln,l,mid);
	init(rn,mid+1,r);
	cr.s=(ls(p).s+rs(p).s)%pp;
	return ;
}

void pushdown(int p,int l,int r){
	ls(p).m=cr.m*ls(p).m%pp;
	ls(p).a=(ls(p).a*cr.m+cr.a)%pp;
	ls(p).s=(ls(p).s*cr.m+cr.a*((mid)-l+1))%pp;
	rs(p).m=cr.m*rs(p).m%pp;
	rs(p).a=(rs(p).a*cr.m+cr.a)%pp;
	rs(p).s=(rs(p).s*cr.m+cr.a*(r- (mid) ))%pp;
	cr.a=0;
	cr.m=1;
}

void ad(int p,int l,int r,ll k){
	if(x<=l&&r<=y){
		cr.s=(cr.s+k*(r-l+1))%pp;
		cr.a=(cr.a+k)%pp;
		return ;
	}
	pushdown(p,l,r);
	if(x<=mid)ad(ln,l,mid,k);
	if(y>mid)ad(rn,mid+1,r,k);
	cr.s=(ls(p).s+rs(p).s)%pp;
}

void ml(int p,int l,int r,ll k){
	if(x<=l&&r<=y){
		cr.s=(cr.s*k)%pp;
		cr.m=(cr.m*k)%pp;
		cr.a=cr.a*k%pp;
		return ;
	}
	pushdown(p,l,r);
	if(x<=mid)ml(ln,l,mid,k);
	if(y>mid)ml(rn,mid+1,r,k);
	cr.s=(ls(p).s+rs(p).s)%pp;
}

ll sm(int p,int l,int r){
	if(x<=l&&r<=y){
		return cr.s;
	}
	pushdown(p,l,r);
	ll su=0;
	if(x<=mid)su+=sm(ln,l,mid);
	if(y>mid)su+=sm(rn,mid+1,r);
	su%=pp;
	return su;
}

void print(int p,int l,int r,int t){
	for(int i=0;i<t;i++)printf("\t");
	printf("P-%d  Sum-%d  Add-%d  Mul-%d L-%d  R-%d\n",p,cr.s,cr.a,cr.m,l,r);
	if(l==r)return ;
	print(ln,l,mid,t+1);
	print(rn,mid+1,r,t+1);
} 

int main(){
	scanf("%d%lld",&n,&pp);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]%=pp;
	init(1,1,n);
	scanf("%d",&m);
	//print(1,1,n,1);
	for(int i=1;i<=m;i++){
		int k;
		scanf("%d",&k);
		if(k==1){
			scanf("%d%d%lld",&x,&y,&xx);
			ml(1,1,n,xx);
		} else if(k==2){
			scanf("%d%d%lld",&x,&y,&xx);
			ad(1,1,n,xx);
		} else {
			scanf("%d%d",&x,&y);
			printf("%lld\n",sm(1,1,n)%pp);
		}
		//print(1,1,n,1);
	}
	return 0;
}



